The present invention relates generally to package tracking systems, and specifically to systems for automatically reading and decoding package information, such as alphanumeric destination addresses.
Postal services and package delivery companies typically handle as many as several million parcels each day. Automated parcel sorting and routing facilities are being used increasingly in order to improve the efficiency and accuracy with which this huge volume of parcels is handled.
The process of sorting and tracking parcels as they proceed through sorting centers requires that each parcel bear two types of information: the destination address of the parcel and a tracking number, which uniquely distinguishes it from other parcels in the system. The information is generally printed on a parcel label, with the destination address in alphanumeric form, and the tracking number in a machine-readable form, such as a barcode. While the destination address tells where the parcel is to go, the tracking number assists the postal service or parcel company in managing its shipment operations and enables it to track parcels as they move through the system. Typically, if the sender of the parcel is a mass mailer who has a contract with the postal service or package company, the tracking number includes a unique code that identifies the sender. In the German postal system, for example, there are about 100,000 such mass-mailer identification codes in use.
In order to sort and route the parcels automatically, the destination address and tracking number are typically read by a high-resolution imaging system. An image processor must then rapidly locate and read the barcode (and/or other machine-readable indicia) and the destination address on the parcel. This task is complicated by the fact that parcels vary greatly in size and shape, and may be placed on a conveyor belt for sorting in substantially any orientation. Furthermore, it frequently occurs that there is other writing on the parcel besides the destination address, such as the return address. Therefore, one of the most difficult problems in automatic parcel sorting is to identify the destination address quickly, correctly and consistently. Otherwise, parcels may be sent to the wrong destination, leading to added expense and customer dissatisfaction.
U.S. Pat. No. 5,103,489, whose disclosure is incorporated herein by reference, describes a label, method and device for locating addresses on articles to be sorted. A specific addressing mark, which typically comprises a ring and an asymmetric logotype, is associated with the address on an addressing label or other addressing support. The addressing mark is chosen so as to enable the address in the digitized image of the article to be located uniquely. To this end, the addressing mark made is inherently different from virtually all characters and graphics likely to be carried by the various articles to be sorted. In other words, location of the address is dependent on customers"" using labels that have a specific mark appearing on the label in a certain position relative to the address.
U.S. Pat. No. 5,770,841, whose disclosure is also incorporated herein by reference, describes a system and method for reading package information. An imaging system captures an image of a package surface that includes a machine-readable code, such as a bar code, and an alphanumeric destination address. The destination address is identified on the package by means of a fluorescent ink fiducial mark located within a destination address block on the package surface. A label decoding system locates and decodes the machine readable code and uses OCR techniques to read the destination address. Thus, in this patent, too, location of the destination address is dependent on customers"" use of a label with a special identifying mark appearing in a fixed relation to the address.
It is an object of some aspects of the present invention to provide improved methods and systems for parcel sorting.
It is a further object of some aspects of the present invention to provide improved methods and systems for automatically identifying the destination address on a parcel label.
It is yet a further object of some aspects of the present invention to provide methods and systems for automatically identifying the destination address on parcel labels without requiring shipping labels to have a particular fixed layout or dedicated identifying marks.
In preferred embodiments of the present invention, a parcel label comprises at least one machine-readable code, typically a barcode, and a destination address. A parcel sorting system identifies and reads the code. The content and/or the position of the code on the label are used to locate the destination address, by comparing the label to known types stored in a memory of the system. If the code identifies a particular mass mailer as the sender of the parcel, the system preferably recalls a known label layout that has been commonly used in the past by this mass mailer. The known layout is then used to find the destination address on the current label, with the position of the code serving as a reference. On the other hand, if the mass mailer or the mailer""s preferred label layout is not known, the position of the code or codes found on the label is compared to a database of known label types or topological classes to which labels may belong. The location of the destination address is then determined by finding the closest match to a known type or class.
Thus, the present invention uses the code on the label to find the destination address rapidly and reliably. There is no need for any special characters or special ink to be used on the label, and mailers are therefore free to use a label of their choice, within broad constraints. The system operates without a priori knowledge of the label layout or type. Preferably, after finding what appears to be the destination address, the system verifies that the address is valid, for example to ensure that the sender and destination addresses have not been accidentally confused.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for automatic sorting, including:
receiving an item in a sequence of items to be sorted, each such item marked with a respective machine-readable identifying code and with respective characters in a location relative to the code that varies from one item to another in the sequence;
determining a position of the code on the item;
responsive to the position of the code, finding the location of the characters on the item; and
processing the characters to determine a destination of the item.
Typically, the items include parcels in shipment, and the code and characters are printed on a label affixed to the item. Preferably, the code includes a barcode.
Preferably, the respective identifying code identifies a sender of the item, and finding the location of the characters includes finding a location based on a known layout of the characters relative to the code, wherein the known layout is associated with the identified sender.
Alternatively or additionally, determining the position of the code includes determining positions of first and second machine-readable codes on the item, and wherein finding the location of the characters includes locating the characters in a coordinate frame defined by the first and second codes. Preferably, locating the characters includes finding a known layout of a marking pattern on some of the items in the sequence based on the positions of the first and second codes, and locating the characters in the known layout. Typically, the marking pattern corresponds to a label affixed to the item, on which the codes and the characters are printed.
Further alternatively or additionally, finding the location of the characters includes:
defining a plurality of topological classes, each class characterized by a common position of the code in a marking pattern on the items in the class and an area, relative to the code, in which the characters are located;
assigning the item to one of the classes based on the position of the code thereon; and
finding the characters in the area that characterizes the class to which the item is assigned.
Preferably, defining the topological classes includes defining classes that are invariant under rotation of the marking pattern. Most preferably, the code includes a barcode, and each class is further characterized by a reading direction of the barcode relative to the marking pattern. Typically, the marking pattern corresponds to a label affixed to the item, on which the codes and the characters are printed, wherein the classes are further characterized by a shape of the label, and wherein assigning the item to one of the classes includes assigning the item responsive to the shape of the label affixed thereto.
In a preferred embodiment, processing the characters includes verifying that the characters represent a valid destination for the item. Preferably, the respective identifying code identifies a sender of the item, and verifying that the characters represent a valid destination includes verifying that the determined destination does not includes an address of the sender.
There is also provided, in accordance with a preferred embodiment of the present invention, a method for automatic sorting, including:
receiving an item in a sequence of items to be sorted, each such item marked with a respective machine-readable code identifying a sender of the item and with respective characters indicative of a destination of the item;
reading the code on the item; and
processing the characters on the item, responsive to the code and to the sender identified thereby, to determine a destination of the item.
Preferably, reading the code includes determining a position of the code on the item, and processing the characters includes finding a location of the characters responsive to the position of the code. Further preferably, reading the code includes identifying the sender responsive to the code, and finding the location of the characters includes associating a layout of the characters relative to the code with the identified sender, and determining the location based on the known layout. Most preferably, associating the layout with the identified sender includes maintaining, for each of a plurality of senders including the identified sender of the item, a respective record of one or more layouts used consistently by the sender to mark the code and characters on the items to be sorted, and selecting the known layout from the respective record. Preferably, maintaining the respective record includes processing multiple items sent by the sender so as to find the one or more layouts used consistently by the sender.
In a preferred embodiment, reading the code includes identifying the sender responsive to the code, and processing the characters includes verifying that the characters represent a valid destination for items sent by the identified sender. Preferably, verifying that the characters represent the valid destination includes verifying that the determined destination does not includes an address of the sender, most preferably by comparing a postal code in the determined destination to a known postal code of the sender. Additionally or alternatively, verifying that the characters represent the valid destination includes comparing words spelled by the characters to a predetermined list of keywords. Further additionally or alternatively, verifying that the characters represent the valid destination includes recognizing that the item has been returned from an original recipient of the item to the sender identified by the code, so that an address of the sender includes the valid destination.
There is additionally provided, in accordance with a preferred embodiment of the present invention, apparatus for automatic sorting, which is configured to receive an item in a sequence of items to be sorted, each such item marked with a respective machine-readable identifying code and with respective characters in a location relative to the code that varies from one item to another in the sequence, the apparatus including a processor, which is adapted to determine a position of the code on the item and, responsive to the position of the code, to find the location of the characters on the item and to process the characters to determine a destination of the item.
In a preferred embodiment, the apparatus includes an imaging device, configured to capture an image of the item, wherein the processor is adapted to process the image in order to determine the destination of the item.
In another preferred embodiment, the apparatus includes an automatic sorter, which is operative to route the item to the determined destination.
There is further provided, in accordance with a preferred embodiment of the present invention, apparatus for automatic sorting, which is configured to receive an item in a sequence of items to be sorted, each such item marked with a respective machine-readable code identifying a sender of the item and with respective characters indicative of a destination of the item, and including a processor, which is operative to read the code on the item and to process the alphanumeric characters on the item, responsive to the code and to the sender identified thereby, to determine a destination of the item.
There is moreover provided, in accordance with a preferred embodiment of the present invention, a computer program product, including a computer-readable medium in which program instructions are stored, which instructions, when read by a computer receiving an image of an item in a sequence of items to be sorted, each such item marked with a respective machine-readable identifying code and with respective characters in a location relative to the code that varies from one item to another in the sequence, cause the computer to determine a position of the code on the item and, responsive to the position of the code, to find the location of the characters on the item and to process the characters to determine a destination of the item.
There is furthermore provided, in accordance with a preferred embodiment of the present invention, a computer program product for automatic sorting, including a computer-readable medium in which program instructions are stored, which instructions, when read by a computer receiving an image of an item in a sequence of items to be sorted, each such item marked with a respective machine-readable code identifying a sender of the item and with respective characters indicative of a destination of the item, cause the computer to read the code on the item, and to process the characters on the item, responsive to the code and to the sender identified thereby, to determine a destination of the item.
The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings in which: